package a1_p04_jw_kw.searchalgo;

import java.util.ArrayList;
import java.util.Set;

import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultWeightedEdge;

import a1_p04_jw_kw.struct.Node;

public class AltBreadthFirstSearch {
	Graph<Node, DefaultWeightedEdge> g;
	Node target;
	private int i = 0;
	public Node[] bestWay;
	private int count = 0;

	public AltBreadthFirstSearch(Graph<Node, DefaultWeightedEdge> g) {
		this.g = g;

	}
	
	public void startSearch(String s, String t) {
		
		Node source = getNode(s);
		this.target = getNode(t);

		// schritt 1: kennzeichen knoten s mit 0
		source.tiefe = 0;
		i = 0;
		count++;
		
		if (bfs()) {
//			System.out.println("Knoten gefunden");
			this.calculateBestWay();
			
		} else {
//			System.out.println("Knoten nicht gefunden");
			
		}
		
		cleanGraph();
		
	}

	public boolean bfs() {

		// wenn keine nachfolger vorhanden, gibt es kein weg zum ziel
		while (true) {

			// schritt 2: nachfolger suchen und markieren
			ArrayList<Node> succesor = new ArrayList<Node>();

			for (Node currentnode : g.vertexSet()) {
				if (currentnode.tiefe == i) {
					succesor.addAll(getSuccessor(currentnode));

				}
			}
			
			if (succesor.isEmpty()) return false;

			// durchsuche alle nachfolger
			for (Node node : succesor) {
				// markiere sie, wenn sie noch nicht markiert waren
				if (node.tiefe == -1) {
					count++;
					node.tiefe = i + 1;

					// wenn t markiert wurde, ist die suche beendet
					if (node.equals(this.target)) {
						return true;
					}
				}
			}

			i++;
		}

	}
	
	private void calculateBestWay() {
		this.bestWay = new Node[this.target.tiefe + 1];
		
		//schritt 1
		int i = this.target.tiefe;
		this.bestWay[i] = this.target;
		
		//schritt 2
		while (i > 0) {
			for (Node predeccesor : getPredecessor(bestWay[i])) {
				if (predeccesor.tiefe == (i - 1)) {
					this.bestWay[i - 1] = predeccesor;
				}
				
			}
			
			i--;
		}
		
	} 

	private ArrayList<Node> getSuccessor(Node node) {
		ArrayList<Node> successor = new ArrayList<Node>();
		Set<DefaultWeightedEdge> edgeSet = g.edgeSet();

		for (DefaultWeightedEdge edge : edgeSet) {
			if (g.getEdgeSource(edge).equals(node)) {
				Node target = g.getEdgeTarget(edge);
				successor.add(target);
			}
		}

		return successor;
	}

	private Node getNode(String name) {
		for (Node node : this.g.vertexSet()) {
			if (node.name.equals(name)) {
				return node;

			}
		}

		return null;
	}
	
	private void cleanGraph() {
		for (Node n : g.vertexSet()) {
			n.tiefe = -1;
			
		}
		
	}
	
	private ArrayList<Node> getPredecessor(Node node) {
		ArrayList<Node> successor = new ArrayList<Node>();
		Set<DefaultWeightedEdge> edgeSet = g.edgeSet();

		for (DefaultWeightedEdge edge : edgeSet) {
			if (g.getEdgeTarget(edge).equals(node)) {
				Node target = g.getEdgeSource(edge);
				successor.add(target);
			}
		}

		return successor;
	}	
	
	public String bestWayToString() {
		String ret = "[";
		for (i = 0; i <= this.bestWay.length-1; i++) {
			ret += "(";
			ret += this.bestWay[i].toString();
			ret += ")";
		}
		
		ret += "]";
		
		
		return ret;
	}

	public int getCount() {
		return count;
	}
	

}
